package main

//78. 子集，回溯方式处理，
//可以考虑二进制求解
// 记原序列中元素的总数为 nnn。原序列中的每个数字
//  的状态可能有两种，即「在子集中」和「不在子集中」。我们用 111 表示「在子集中」，000 表示不在子集中，那么每一个子集可以对应一个长度为 nnn 的 0/10/10/1 序列，第 iii 位表示 aia_ia
//  是否在子集中。例如，n=3n = 3n=3 ，a={5,2,9}a = \{ 5, 2, 9 \}a={5,2,9} 时：
func main() {
	nums := []int{1, 2, 3}
	res := subsets(nums)
	for _, l := range res {
		for _, i := range l {
			print(i)
		}
		println()
	}
}

func subsets(nums []int) [][]int {
	var set []int
	var res [][]int
	var dfs func(curr int)
	dfs = func(curr int) {
		if curr == len(nums) {
			res = append(res, append([]int{}, set...))
			return
		}
		set = append(set, nums[curr])
		dfs(curr + 1)
		set = set[0 : len(set)-1]
		dfs(curr + 1)
	}
	dfs(0)
	return res
}

func subsets2(nums []int) (ans [][]int) {
	n := len(nums)
	for mask := 0; mask < 1<<n; mask++ {
		set := []int{}
		for i, v := range nums {
			if mask>>i&1 > 0 {
				set = append(set, v)
			}
		}
		ans = append(ans, append([]int(nil), set...))
	}
	return
}

// 78. 子集
//中等
//相关标签
//相关企业
//给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
//子集
//（幂集）。
//
//解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
//
//
//
//示例 1：
//
//输入：nums = [1,2,3]
//输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//示例 2：
//
//输入：nums = [0]
//输出：[[],[0]]
//
//
//提示：
//
//1 <= nums.length <= 10
//-10 <= nums[i] <= 10
//nums 中的所有元素 互不相同
